
import java.util.HashMap;
import java.util.LinkedList;

/**
 *
 * @author Jah Emanuel
 */
public class Graph {

    private int[][] graph;
    private int[] horizontalSum;
    private boolean isDirected;
    private HashMap<String, Integer> mappingValuesToIndexes;
    private HashMap<Integer, String> mappingIndexesToValues;
    private LinkedList<LinkedList<Integer>> prohibitions;
    private int maxSlots;

    public Graph(boolean isDirected, LinkedList<String[]> connections, LinkedList<String[]> restrictions) throws InvalidStringFormat, Exception {
        prohibitions = new LinkedList<LinkedList<Integer>>();
        maxSlots = Integer.MAX_VALUE;
        this.isDirected = isDirected;
        mappingValuesToIndexes = new HashMap<String, Integer>();
        mappingIndexesToValues = new HashMap<Integer, String>();
        fillMappingValues(connections);
        graph = new int[mappingValuesToIndexes.size()][mappingValuesToIndexes.size()];
        horizontalSum = new int[mappingValuesToIndexes.size()];
        for (int i = 0; i < mappingValuesToIndexes.size(); i++) {
            prohibitions.add(new LinkedList<Integer>());
        }
        fillGraphConnections(connections);
        processRestrictions(restrictions);
    }

    public Graph() {
    }

    public boolean isDirected() {
        return isDirected;
    }

    public HashMap<Integer, String> getMappingIndexesToValues() {
        return mappingIndexesToValues;
    }

    public int[] getHorizontalSum() {
        return horizontalSum;
    }

    public int getMaxSlots() {
        return maxSlots;
    }

    public int[][] getGraph() {
        return graph;
    }

    public LinkedList<LinkedList<Integer>> getProhibitions() {
        return prohibitions;
    }
    
    

    private void fillMappingValues(LinkedList<String[]> connections) {
        String[] arrAux;
        int index = 0;
        for (int i = 0; i < connections.size(); i++) {
            arrAux = connections.get(i);
            for (int j = 0; j < arrAux.length; j++) {
                if (!mappingValuesToIndexes.containsKey(arrAux[j])) {
                    mappingIndexesToValues.put(index, arrAux[j]);
                    mappingValuesToIndexes.put(arrAux[j], index++);
                }
            }
        }
    }

    private void fillGraphConnections(LinkedList<String[]> connections) throws InvalidStringFormat, Exception {
        if (isDirected) {
            int indexSource;
            int indexDestination;
            for (String[] strings : connections) {
                indexSource = mappingValuesToIndexes.get(strings[0]);
                indexDestination = mappingValuesToIndexes.get(strings[1]);
                if (indexSource != indexDestination) {
                    if (graph[indexSource][indexDestination] == 0) {
                        graph[indexSource][indexDestination] = 1;
                    }
                } else {
                    throw new InvalidStringFormat("The source and destination must be different. [" + strings[0] + ":" + strings[1] + "]");
                }
            }
            boolean[] visited;
            for (int i = 0; i < graph.length; i++) {
                visited = new boolean[graph.length];
                fillHorizontalSumDirectedGraph(i,i, visited);
                horizontalSum[i]=0;
                for(int j=0;j<graph.length;j++){
                    if(visited[j]){
                        horizontalSum[i]++;
                        graph[i][j]=1;
                    }
                }
            }
        } else {
            int indexSource;
            int indexDestination;
            for (String[] strings : connections) {
                for (int source = 0; source < strings.length; source++) {
                    for (int destination = 0; destination < strings.length; destination++) {
                        if (source != destination) {
                            indexSource = mappingValuesToIndexes.get(strings[source]);
                            indexDestination = mappingValuesToIndexes.get(strings[destination]);
                            if (indexSource != indexDestination) {
                                if (graph[indexSource][indexDestination] == 0) {
                                    graph[indexSource][indexDestination] = 1;
                                    horizontalSum[indexSource]++;
                                }
                            } else {
                                throw new InvalidStringFormat("The source and destination must be different.");
                            }
                        }
                    }
                }
            }
        }
    }
    
    private void fillHorizontalSumDirectedGraph(int source, int node, boolean [] visited)throws Exception{
        for (int j = 0; j < graph[node].length; j++) {
            if(j!=node){
                if (graph[node][j] == 1) {
                    visited[j] = true;
                    if(visited[source]){
                        throw new Exception("Graph contains a cycle.");
                    }
                    fillHorizontalSumDirectedGraph(source, j, visited);
                }
            }
        }
    }

    private void processRestrictions(LinkedList<String[]> restrictions) throws InvalidStringFormat, Exception {
        int indexRestrictionNode;
        int numRest;
        String logicalRest;
        for (String[] rest : restrictions) {
            if (rest[0].equals("H")) {
                indexRestrictionNode = mappingValuesToIndexes.get(rest[1]);
                logicalRest = rest[2].substring(0, 2);
                numRest = Integer.parseInt(rest[2].substring(2));
                addHRestriction(indexRestrictionNode, logicalRest, numRest - 1);
            } else if (rest[0].equals("S")) {
                if (maxSlots == Integer.MAX_VALUE) {
                    numRest = Integer.parseInt(rest[1].substring(2));
                    maxSlots = numRest;
                } else {
                    throw new InvalidStringFormat("Two restrictions defined for 'S'.");
                }
            } else {
                throw new InvalidStringFormat("Restriction undefined: " + rest[0]);
            }
        }
    }

    private void addHRestriction(int indexNode, String logicalRest, int numRest) throws Exception {
        if (logicalRest.equals("!=")) {
            prohibitions.get(indexNode).add(numRest);
        } else if (logicalRest.equals(">=")) {
            for (int i = 0; i < numRest; i++) {
                prohibitions.get(indexNode).add(i);
            }
        } else if (logicalRest.equals(">>")) {
            for (int i = 0; i <= numRest; i++) {
                prohibitions.get(indexNode).add(i);
            }
        }
        if (isDirected) {
            boolean[] visited;
            for (int i = 0; i < graph.length; i++) {
                visited = new boolean[graph.length];
                prohibitionsForChildren(i,i, visited);
                if(visited[i]){
                    throw new Exception("Graph contains a cycle.");
                }
            }
        }
    }

    private void prohibitionsForChildren(int source, int node, boolean[] visited)throws Exception{
        LinkedList<Integer> prohibitionsNodeI;
        LinkedList<Integer> prohibitionsNodeJ;
        prohibitionsNodeI = prohibitions.get(node);
        for (int j = 0; j < graph[node].length; j++) {
            if(j!=node){
                if (graph[node][j] == 1) {
                    visited[j] = true;
                    if(visited[source]){
                        throw new Exception("Graph contains a cycle.");
                    }
                    prohibitionsNodeJ = prohibitions.get(j);
                    for (Integer integer : prohibitionsNodeI) {
                        if (!prohibitionsNodeJ.contains(integer)) {
                            prohibitionsNodeJ.add(integer);
                        }
                    }
                    prohibitionsForChildren(source,j, visited);
                }
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (isDirected) {
            sb.append("Directed");
        } else {
            sb.append("Undirected");
        }
        sb.append(" Graph\n\n");
        sb.append("    ");
        for (int i = 0; i < mappingIndexesToValues.size(); i++) {
            sb.append(String.format("%1$-" + 4 + "s", mappingIndexesToValues.get(i)));
        }
        sb.append("SUM");


        sb.append("\n\n");

        for (int i = 0; i < graph.length; i++) {
            sb.append(String.format("%1$-" + 4 + "s", mappingIndexesToValues.get(i)));
            for (int j = 0; j < graph.length; j++) {
                sb.append(String.format("%1$-" + 4 + "s", graph[i][j]));
                //sb.append(graph[i][j]+"\t");
            }
            sb.append(String.format("%1$-" + 4 + "s", horizontalSum[i]));
            //sb.append(horizontalSum[i]+"\t");
            sb.append("\n");
        }
        sb.append("\n\n");

        sb.append("Initial restrictions\n");
        int i = 0;
        for (LinkedList<Integer> list : prohibitions) {
            sb.append(mappingIndexesToValues.get(i++) + ": ");
            for (Integer integer : list) {
                sb.append(integer +1 + ",");
            }
            sb.append("\n");
        }

        return sb.toString();
    }
}
